package com.yiwenup.leetcode.offer;

import com.yiwenup.leetcode.ListNode;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/
 **/
public class No052 {
    /**
     * 执行用时：882 ms, 在所有 Java 提交中击败了5.02%的用户
     * 内存消耗：41.4 MB, 在所有 Java 提交中击败了11.62%的用户
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        List<ListNode> list = new ArrayList<>();
        ListNode cur = headA;
        while (cur != null) {
            list.add(cur);
            cur = cur.next;
        }

        cur = headB;
        while (cur != null) {
            if (list.contains(cur)) {
                return cur;
            }
            cur = cur.next;
        }

        return null;
    }

    /**
     * 执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：40.9 MB, 在所有 Java 提交中击败了88.80%的用户
     */
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        int lenA = len(headA);
        int lenB = len(headB);
        ListNode curA = headA;
        ListNode curB = headB;
        if (lenA > lenB) {
            int distance = lenA - lenB;
            while (distance > 0) {
                curA = curA.next;
                distance--;
            }
        } else {
            int distance = lenB - lenA;
            while (distance > 0) {
                curB = curB.next;
                distance--;
            }
        }

        while (curA != curB) {
            curA = curA.next;
            curB = curB.next;
        }

        return curA;
    }

    private int len(ListNode node) {
        int length = 0;
        while (node != null) {
            length++;
            node = node.next;
        }
        return length;
    }

    /**
     * 执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：41.2 MB, 在所有 Java 提交中击败了52.25%的用户
     */
    public ListNode getIntersectionNode3(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;

        while (curA != curB) {
            curA = curA == null ? headB : curA.next;
            curB = curB == null ? headA : curB.next;
        }

        return curA;
    }
}
